home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / bisonpcb / closure.c < prev    next >
C/C++ Source or Header  |  1987-02-12  |  8KB  |  373 lines
  1. /* Subroutines for bison
  2.    Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
  3.   
  4. BISON is distributed in the hope that it will be useful, but WITHOUT ANY
  5. WARRANTY.  No author or distributor accepts responsibility to anyone
  6. for the consequences of using it or for whether it serves any
  7. particular purpose or works at all, unless he says so in writing.
  8. Refer to the BISON General Public License for full details.
  9.   
  10. Everyone is granted permission to copy, modify and redistribute BISON,
  11. but only under the conditions described in the BISON General Public
  12. License.  A copy of this license is supposed to have been given to you
  13. along with BISON so you can know your rights and responsibilities.  It
  14. should be in a file named COPYING.  Among other things, the copyright
  15. notice and this notice must be preserved on all copies.
  16.   
  17.  In other words, you are welcome to use, share and improve this program.
  18.  You are forbidden to forbid anyone else to use, share and improve
  19.  what you give them.   Help stamp out software-hoarding!  */
  20.  
  21. /* subroutines of file LR0.c.
  22.   
  23. Entry points:
  24.   
  25.   closure (items, n)
  26.   
  27. Given a vector of item numbers items, of length n,
  28. set up ruleset and itemset to indicate what rules could be run
  29. and which items could be accepted when those items are the active ones.
  30.   
  31. ruleset contains a bit for each rule.  closure sets the bits
  32. for all rules which could potentially describe the next input to be read.
  33.   
  34. itemset is a vector of item numbers; itemsetend points to just beyond the end
  35.  of the part of it that is significant.
  36. closure places there the indices of all items which represent units of
  37. input that could arrive next.
  38.   
  39.   initialize_closure (n)
  40.   
  41. Allocates the itemset and ruleset vectors,
  42. and precomputes useful data so that closure can be called.
  43. n is the number of elements to allocate for itemset.
  44.   
  45.   finalize_closure ()
  46.   
  47. Frees itemset, ruleset and internal data.
  48.   
  49. */
  50.  
  51.  
  52. /*
  53.  * Port to PC by Whit Gregg
  54.  *               Nourse, Gregg & Browne, Inc.
  55.  *         1 Horizon Road
  56.  *         Fort Lee, NJ  07024
  57.  */
  58.  
  59.  
  60.  
  61. #include <stdio.h>
  62. #include <malloc.h>
  63. #include "machine.h"
  64. #include "new.h"
  65. #include "gram.h"
  66. #include "func.h"
  67.  
  68.  
  69.     extern short **derives;
  70.  
  71.  
  72. short *itemset;
  73. short *itemsetend;
  74. static unsigned *ruleset;
  75.  
  76. /* internal data.  See comments before set_fderives and set_firsts.  */
  77. static unsigned *fderives;
  78. static unsigned *firsts;
  79.  
  80. /* number of words required to hold a bit for each rule */
  81. static int rulesetsize;
  82.  
  83. /* number of words required to hold a bit for each variable */
  84. static int varsetsize;
  85.  
  86.  
  87.  
  88. void 
  89. initialize_closure(n)        /* WG */
  90.     int n;
  91. {
  92.     itemset = NEW2(n, short);
  93.  
  94.     rulesetsize = WORDSIZE(nrules + 1);
  95.     ruleset = NEW2(rulesetsize, unsigned);
  96.  
  97.     set_fderives();
  98.     }
  99.  
  100.  
  101.  
  102. /* set fderives to an nvars by nrules matrix of bits
  103.    indicating which rules can help derive the beginning of the data
  104.    for each nonterminal.  For example, if symbol 5 can be derived as
  105.    the sequence of symbols 8 3 20, and one of the rules for deriving
  106.    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
  107.  
  108. void 
  109. set_fderives()
  110. {                /* WG */
  111.     register unsigned *rrow;
  112.     register unsigned *vrow;
  113.     register int j;
  114.     register unsigned mask;
  115.     register unsigned cword;
  116.     register short *rp;
  117.  
  118.     int ruleno;
  119.     int i;
  120.  
  121.     fderives = NEW2(nvars * rulesetsize, unsigned) -ntokens * rulesetsize;
  122.  
  123.     set_firsts();
  124.  
  125.     rrow = fderives + ntokens * rulesetsize;
  126.  
  127.     for (i = ntokens; i < nsyms; i++) {
  128.         vrow = firsts + ((i - ntokens) * varsetsize);
  129.         cword = *vrow++;
  130.         mask = 1;
  131.         for (j = ntokens; j < nsyms; j++) {
  132.             if (cword & mask) {
  133.                 rp = derives[j];
  134.                 while ((ruleno = *rp++) > 0) {
  135.                     SETBIT(rrow, ruleno);
  136.                     }
  137.                 }
  138.  
  139.             mask <<= 1;
  140.             if (mask == 0) {
  141.                 cword = *vrow++;
  142.                 mask = 1;
  143.                 }
  144.             }
  145.  
  146.         vrow += varsetsize;
  147.         rrow += rulesetsize;
  148.         }
  149.  
  150. #ifdef    DEBUG
  151.     print_fderives();
  152. #endif
  153.  
  154.     FREE(firsts);
  155.     }
  156.  
  157.  
  158.  
  159. /* set firsts to be an nvars by nvars bit matrix indicating which items
  160.    can represent the beginning of the input corresponding to which other items.
  161.    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
  162.    the symbol 8 can be the beginning of the data for symbol 5,
  163.    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
  164.  
  165. void 
  166. set_firsts()
  167. {                /* WG */
  168.     register unsigned *row;
  169.  
  170. /*   register int done; JF unused */
  171.     register int symbol;
  172.     register short *sp;
  173.     register int rowsize;
  174.  
  175.     int i;
  176.  
  177.     varsetsize = rowsize = WORDSIZE(nvars);
  178.  
  179.     firsts = NEW2(nvars * rowsize, unsigned);
  180.  
  181.     row = firsts;
  182.     for (i = ntokens; i < nsyms; i++) {
  183.         sp = derives[i];
  184.         while (*sp >= 0) {
  185.             symbol = ritem[rrhs[*sp++]];
  186.             if (ISVAR(symbol)) {
  187.                 symbol -= ntokens;
  188.                 SETBIT(row, symbol);
  189.                 }
  190.             }
  191.  
  192.         row += rowsize;
  193.         }
  194.  
  195.     RTC(firsts, nvars);
  196.  
  197. #ifdef    DEBUG
  198.     print_firsts();
  199. #endif
  200.     }
  201.  
  202.  
  203.  
  204. void 
  205. closure(core, n)        /* WG */
  206.     short *core;
  207.     int n;
  208. {
  209.     register int ruleno;
  210.     register unsigned word;
  211.     register unsigned mask;
  212.     register short *csp;
  213.     register unsigned *dsp;
  214.     register unsigned *rsp;
  215.  
  216.     short *csend;
  217.     unsigned *rsend;
  218.     int symbol;
  219.     int itemno;
  220.  
  221.     rsp = ruleset;
  222.     rsend = ruleset + rulesetsize;
  223.     csend = core + n;
  224.  
  225.     if (n == 0) {
  226.         dsp = fderives + start_symbol * rulesetsize;
  227.         while (rsp < rsend)
  228.             *rsp++ = *dsp++;
  229.         }
  230.     else {
  231.         while (rsp < rsend)
  232.             *rsp++ = 0;
  233.  
  234.         csp = core;
  235.         while (csp < csend) {
  236.             symbol = ritem[*csp++];
  237.             if (ISVAR(symbol)) {
  238.                 dsp = fderives + symbol * rulesetsize;
  239.                 rsp = ruleset;
  240.                 while (rsp < rsend)
  241.                     *rsp++ |= *dsp++;
  242.                 }
  243.             }
  244.         }
  245.  
  246.     ruleno = 0;
  247.     itemsetend = itemset;
  248.     csp = core;
  249.     rsp = ruleset;
  250.     while (rsp < rsend) {
  251.         word = *rsp++;
  252.         if (word == 0) {
  253.             ruleno += BITS_PER_WORD;
  254.             }
  255.         else {
  256.             mask = 1;
  257.             while (mask) {
  258.                 if (word & mask) {
  259.                     itemno = rrhs[ruleno];
  260.                     while (csp < csend && *csp < itemno)
  261.                         *itemsetend++ = *csp++;
  262.                     *itemsetend++ = itemno;
  263.                     }
  264.  
  265.                 mask <<= 1;
  266.                 ruleno++;
  267.                 }
  268.             }
  269.         }
  270.  
  271.     while (csp < csend)
  272.         *itemsetend++ = *csp++;
  273.  
  274. #ifdef    DEBUG
  275.     print_closure(n);
  276. #endif
  277.     }
  278.  
  279.  
  280.  
  281. void 
  282. finalize_closure()
  283. {                /* WG */
  284.     FREE(itemset);
  285.     FREE(ruleset);
  286.     FREE(fderives + ntokens * rulesetsize);
  287.     }
  288.  
  289.  
  290.  
  291. #ifdef    DEBUG
  292.  
  293. print_closure(n)
  294.     int n;
  295. {
  296.     register short *isp;
  297.  
  298.     printf("\n\nn = %d\n\n", n);
  299.     for (isp = itemset; isp < itemsetend; isp++)
  300.         printf("   %d\n", *isp);
  301.     }
  302.  
  303.  
  304.  
  305. print_firsts()
  306. {
  307.     register int i;
  308.     register int j;
  309.     register unsigned *rowp;
  310.     register unsigned cword;
  311.     register unsigned mask;
  312.  
  313.     extern char **tags;
  314.  
  315.     printf("\n\n\nFIRSTS\n\n");
  316.  
  317.     for (i = ntokens; i < nsyms; i++) {
  318.         printf("\n\n%s firsts\n\n", tags[i]);
  319.  
  320.         rowp = firsts + ((i - ntokens) * vrowsize);
  321.  
  322.         cword = *rowp++;
  323.         mask = 1;
  324.         for (j = 0; j < nsyms; j++) {
  325.             if (cword & mask)
  326.                 printf("   %s\n", tags[j + ntokens]);
  327.  
  328.             mask <<= 1;
  329.  
  330.             if (mask == 0) {
  331.                 cword = *rowp++;
  332.                 mask = 1;
  333.                 }
  334.             }
  335.         }
  336.     }
  337.  
  338.  
  339.  
  340. print_fderives()
  341. {
  342.     register int i;
  343.     register int j;
  344.     register unsigned *rp;
  345.     register unsigned cword;
  346.     register unsigned mask;
  347.  
  348.     extern char **tags;
  349.  
  350.     printf("\n\n\nFDERIVES\n");
  351.  
  352.     for (i = ntokens; i < nsyms; i++) {
  353.         printf("\n\n%s derives\n\n", tags[i]);
  354.         rp = fderives + i * rrowsize;
  355.         cword = *rp++;
  356.         mask = 1;
  357.         for (j = 0; j <= nrules; j++) {
  358.             if (cword & mask)
  359.                 printf("   %d\n", j);
  360.  
  361.             mask <<= 1;
  362.             if (mask == 0) {
  363.                 cword = *rp++;
  364.                 mask = 1;
  365.                 }
  366.             }
  367.         }
  368.  
  369.     fflush(stdout);
  370.     }
  371.  
  372. #endif
  373.